<!DOCTYPE html>
<html lang="en">
<head>
  <meta charset="UTF-8">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <title>Document</title>
</head>
<body>
  <script>
    /**
     * 链表与数组
     * 1 数组是连续的存储空间，链表是无序的，可以存放在任意位置
     * 2 数组都是固定大小的，链表没有固定大小，可以任意扩展
     * 3 数组插入元素每次都需要申请新的数组空间，写入新的数组，链表只需要修改节点的next值
     * 4 数组删除元素都需要移动很多元素，链表，只需要修改节点的next值
     * 5 数据查找非常快速，只需要按照下标查找就可以，链表查找元素每次都需要从header开始
    */
    function LinkedList() {
      this.header = null
      this.length = 0

      function LinkedItem(data) {
        this.data = data
        this.next = null
      }
      // 添加新节点
      LinkedList.prototype.append = (data) => {
        // 1 创建链表新节点
        var item = new LinkedItem(data)
        // 2 先判断，链表是否是空链表，是的话，就先给header添加节点
        if (this.length === 0) {
          this.header = item
        } else {
          // 3 如果不是空节点，就需要借用指针从头开始找最后一个节点
          // 原理是最后一个节点的next肯定是空的，因为中间的节点next都会指向下一个节点
          // 先从header开始查找，判断每个节点是否为Null,不是null的话就指向该节点的next
          // 因为该节点的next就是下一个节点，当发现current.next为null时，说明就找到了
          // 最后一个节点，然后将该节点的next指向新的节点就可以
          var current = this.header
          while (current.next) {
            current = current.next
          }
          current.next = item
        }
        this.length += 1
      }
      // 插入新节点，注意边界
      LinkedList.prototype.insert = (data, position) => {
        // 1 先检查边界问题，小于0和大于链表长度的位置都是不行的
        if (position < 0 || position > this.length) {
          alert('超出了链表的范围，请检查插入位置是否正确')
          return
        }

        var item = new LinkedItem(data)
        // 2 如果在第一个位置插入，直接切换header即可
        if (position === 0) {
          item.next = this.header
          this.header = item
        } else {
          var current = this.header
          var previous = null
          var index = 0
          // 如果在后面的位置插入数据
          // 通过循环，查找到当前位置，然后将前一个节点存储，用current指向当前节点
          // 找到当前位置之后，要将前一个节点的next指向插入的元素，将插入元素的next指向当前节点
          while (index < position) {
            index++
            previous = current
            current = current.next
          }
          item.next = current
          previous.next = item
        }
      }
      LinkedList.prototype.toString = () => {
        var str = ''
        var current = this.header
        while(current.next) {
          str += current.data + '=====>'
          current = current.next
        }
        return str
      }
    }
    var list = new LinkedList()
    list.append('aaaa')
    list.append('bbbb')
    list.append('cccc')
    list.append('dddd')
    list.append('eeee')
    alert(list)
    list.insert('22222', 2)
    alert(list)
    list.insert('4444', 4)
    alert(list)
    list.insert('6666', 5)
    alert(list)
  </script>
</body>
</html>